package com.yanceysong.codetop.s31_s40;

import com.yanceysong.common.ListNode;

import java.util.Deque;
import java.util.LinkedList;


public class S37_Mid_19_删除链表的倒数第N个节点 {
    /**
     * 题目: 19. 删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)
     * LeetCode: <a href="https://leetcode.cn/problems/remove-nth-node-from-end-of-list/">...</a>
     * ----------------------------------------------------------------------
     * 描述:
     * 给定一个链表的头节点 head，删除链表中倒数第 n 个节点，并返回新的头节点。
     * 保证 n 一定有效 (1 <= n <= 链表长度)。
     * ----------------------------------------------------------------------
     * 示例 1:
     * 输入: head = [1,2,3,4,5], n = 2
     * 输出: [1,2,3,5]
     * 解释: 倒数第2个节点是值 4 的节点。
     * <p>
     * 示例 2:
     * 输入: head = [1], n = 1
     * 输出: []
     * <p>
     * 示例 3:
     * 输入: head = [1,2], n = 1
     * 输出: [1]
     * <p>
     * 示例 4:
     * 输入: head = [1,2], n = 2
     * 输出: [2]
     * ----------------------------------------------------------------------
     * 核心思路 (单遍双指针 / 快慢指针窗口):
     * 1. 设两个指针 ahead 与 lag，ahead 先向前走 n 步，形成“间隔 n”。
     * 2. 之后 ahead 与 lag 同步向前。
     * 3. 当 ahead 到达链表末尾 (null) 时，lag 正好停在“待删除节点的前一个节点”。
     * 4. 直接执行 lag.next = lag.next.next 即可删除目标节点。
     * 5. 使用哨兵节点 dummy 统一处理“删除头节点”的情况。
     * <p>
     * ASCII 图解 (示例 head=[1,2,3,4,5], n=2):
     * . 初始(含dummy):  D -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     * . 第一步 ahead 先走2步: (间隔建立)
     * .   ahead: 指向节点 3
     * .   lag:   指向 D
     * . 同步推进:
     * .   1) ahead=4, lag=1
     * .   2) ahead=5, lag=2
     * .   3) ahead=null, lag=3  (停止)
     * . lag.next = 4 (目标删除), 修改为 lag.next = 5
     * . 结果: D -> 1 -> 2 -> 3 -> 5
     * ----------------------------------------------------------------------
     * 复杂度分析:
     * - 时间: O(L)  L 为链表长度, 只单次遍历。
     * - 空间: O(1)  仅常数额外指针。
     * ----------------------------------------------------------------------
     * 关键洞察 / 易错点:
     * 1. 删除头节点时 (n == length) 必须靠 dummy 处理，否则无法访问其前驱。
     * 2. 先走 n 步时 n 恰等于长度, ahead 会直接到 null; 此时 lag 仍在 dummy, 删除的是原 head。
     * 3. 不要在 while 循环内用 (ahead.next != null) 作为条件; 应用 (ahead != null) 保证 lag 最终停到目标前驱。
     * 4. 建立间隔时的 for 循环不需要判空 (题目保证 n 有效)。
     * ----------------------------------------------------------------------
     * 其它可选方案:
     * 1) 两遍法: 第一遍统计长度 L，第二遍走到 (L-n) 的前驱节点删除 (时间 O(L), 简单但两遍)。
     * 2) 栈: 遍历压栈后弹出 n 个节点找到前驱 (时间 O(L), 空间 O(L)).
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 哨兵节点 (dummy) 统一处理删除头节点等边界情形
        ListNode dummy = new ListNode(0, head);
        // ahead: 先行指针，用来创建 n 的间隔
        ListNode ahead = head;
        // lag: 滞后指针，定位到待删除节点的前驱
        ListNode lag = dummy;
        // 1. ahead 先走 n 步，建立间隔 (题目保证 n 合法，无需判空)
        for (int i = 0; i < n; i++) {
            ahead = ahead.next;
        }
        // 2. 同步前进, 直到 ahead 走到 null
        while (ahead != null) {
            ahead = ahead.next;
            lag = lag.next;
        }
        // 3. 删除 lag 之后的那个节点 (倒数第 n 个)
        lag.next = lag.next.next;
        // 4. 返回新头 (可能已变化)
        return dummy.next;
    }

    /**
     * 备选实现: 栈方式 (演示, 非必须)。
     * 压栈所有节点, 弹出 n 个, 栈顶即删除节点的前驱。
     * 时间 O(L), 空间 O(L)
     */
    public ListNode removeNthFromEndWithStack(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = dummy;
        while (cur != null) { // 压栈所有 (含 dummy 方便定位前驱)
            stack.push(cur);
            cur = cur.next;
        }
        // 弹出 n 个, 此时栈顶是待删除节点的前驱
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    // ============================ 测试与工具方法 ============================

    public static void main(String[] args) {
        S37_Mid_19_删除链表的倒数第N个节点 solver = new S37_Mid_19_删除链表的倒数第N个节点();
        System.out.println("=== 删除链表的倒数第 N 个结点 测试开始 ===\n");

        // 用例1: 题目示例 [1,2,3,4,5], n=2 -> [1,2,3,5]
        testCase(solver, new int[]{1, 2, 3, 4, 5}, 2, new int[]{1, 2, 3, 5}, "示例1: 删除倒数第二个 (删除4)");

        // 用例2: 单节点删除自身 [1], n=1 -> []
        testCase(solver, new int[]{1}, 1, new int[]{}, "示例2: 单节点删除");

        // 用例3: 两节点删除最后一个 [1,2], n=1 -> [1]
        testCase(solver, new int[]{1, 2}, 1, new int[]{1}, "示例3: 删除尾节点");

        // 用例4: 两节点删除头节点 [1,2], n=2 -> [2]
        testCase(solver, new int[]{1, 2}, 2, new int[]{2}, "示例4: 删除头节点");

        // 用例5: 删除中间 ( [1,2,3], n=2 -> [1,3] )
        testCase(solver, new int[]{1, 2, 3}, 2, new int[]{1, 3}, "示例5: 删除中间节点2");

        // 用例6: n 等于长度 ( [1,2,3,4], n=4 -> [2,3,4] )
        testCase(solver, new int[]{1, 2, 3, 4}, 4, new int[]{2, 3, 4}, "示例6: n等于长度删除头");

        // 用例7: 较长链表删除倒数第1个 (尾部) [1..8], n=1 -> [1..7]
        testCase(solver, new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 1, new int[]{1, 2, 3, 4, 5, 6, 7}, "示例7: 删除尾部8");

        // 用例8: 较长链表删除倒数第5个 ( [1..8], n=5 -> 删除4 )
        testCase(solver, new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 5, new int[]{1, 2, 3, 5, 6, 7, 8}, "示例8: 删除值4");

        // 用例9: 使用栈解法对比 ( [10,20,30,40], n=3 -> 删除20 )
        ListNode stackResult = solver.removeNthFromEndWithStack(buildList(new int[]{10, 20, 30, 40}), 3);
        assert listEquals(stackResult, buildList(new int[]{10, 30, 40})) : "栈解法结果错误";
        System.out.println("[通过] 示例9: 栈解法删除倒数第3个 (值20)");

        System.out.println("\n=== 所有测试用例通过 ===");
    }

    // 单个测试用例执行
    private static void testCase(S37_Mid_19_删除链表的倒数第N个节点 solver, int[] input, int n, int[] expect, String title) {
        ListNode head = buildList(input);
        ListNode result = solver.removeNthFromEnd(head, n);
        boolean ok = listEquals(result, buildList(expect));
        System.out.println((ok ? "[通过] " : "[失败] ") + title + " -> 输出: " + listToString(result) + ", 期望: " + arrayToString(expect));
        assert ok : title + " 未通过";
    }

    // 构造链表
    private static ListNode buildList(int[] arr) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    // 链表比较
    private static boolean listEquals(ListNode a, ListNode b) {
        while (a != null && b != null) {
            if (a.val != b.val) return false;
            a = a.next;
            b = b.next;
        }
        return a == null && b == null;
    }

    // 打印链表
    private static String listToString(ListNode head) {
        StringBuilder sb = new StringBuilder();
        ListNode cur = head;
        while (cur != null) {
            sb.append(cur.val);
            if (cur.next != null) sb.append("->");
            cur = cur.next;
        }
        return sb.toString();
    }

    private static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append("->");
        }
        return sb.toString();
    }
}
